import java.util.*;

public class Main {
    static Random rn = new Random(System.currentTimeMillis());
    public static int getRandomInt(int i){
        return Math.abs(rn.nextInt())%i + 1;
    }
    public static String getRandomOperator(){
        int i = getRandomInt(3);
        if(i==1){
            return "+";
        }else if(i==2){
            return "-";
        }else {
            return "*";
        }
    }

    public String generateParenth(int l){
        StringBuilder sb = new StringBuilder();
        int j =0;
        for(int i=0;i<l;i++){
            if(i>0 && sb.charAt(sb.length()-1)==')'){
                sb.append(getRandomOperator());
            }
            sb.append("(");
            if(i==l-1){
                sb.append(generateSimpleExpression(getRandomInt(3)+1));
                sb.append(")");
                j++;
            }else {
                if (getRandomInt(2) == 1) {
                    sb.append(generateSimpleExpression(getRandomInt(3) + 1));
                    sb.append(")");
                    j++;
                } else {
                    if (getRandomInt(2) == 1) {
                        sb.append(generateSimpleExpression(2));
                        sb.append(getRandomOperator());
                    }
                }
            }
        }
        for(;j<l;j++){
            if(getRandomInt(2)==1){
                sb.append(getRandomOperator());
                sb.append(generateSimpleExpression(2));
                sb.append(")");
            }else {
                sb.append(")");
            }
        }
        return sb.toString();
    }

    public String generateSimpleExpression(int l){
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<l;i++){
            sb.append(getRandomInt(50));
            if(i!=l-1) {
                sb.append(getRandomOperator());
            }
        }
        return sb.toString();
    }

    public String generateExpression(int length) {
        StringBuilder sb = new StringBuilder();
        String pathPattern = generateParenth(length);
        // expression before path
        if (getRandomInt(2)==1){
            sb.append(generateSimpleExpression(getRandomInt(2)+1));
            sb.append(getRandomOperator());
        }
        // expression with path
        sb.append(pathPattern);

        // expression suffix
        if (getRandomInt(2)==1){
            sb.append(getRandomOperator());
            sb.append(generateSimpleExpression(getRandomInt(2)+1));
        }
        return sb.toString();
    }

    public void testWithStr(String str, int expected){
        Solution solution = new Solution();

        int actual = solution.calculate(str);
        if(actual != expected){
            String msg = "Test Failed\n";
            msg += "Input:" + str + "\n";
            msg += "Expected:" + expected + "\n";
            msg += "Actual:" + actual;
            throw new RuntimeException(msg);
        }
    }

    public void testFunc(){
        String str = generateExpression(getRandomInt(4)+1);
        //System.out.println("generated expression");
        //System.out.println(str);
        testWithStr(str, evaluate(str));
    }

    public static void main(String[] args) {
        try {
            Main main = new Main();
            //main.testWithStr("99999999*99999999", 0);
            for(int i=0;i<20;i++) {
                main.testFunc();
            }
        }catch (Exception ex){
            System.out.println(ex.getMessage());
            System.exit(-1);
        }
    }
    public static int evaluate(String expression)
    {
        char[] tokens = expression.toCharArray();

        // Stack for numbers: 'values'
        Stack<Integer> values = new
                Stack<Integer>();

        // Stack for Operators: 'ops'
        Stack<Character> ops = new
                Stack<Character>();

        for (int i = 0; i < tokens.length; i++)
        {

            // Current token is a
            // whitespace, skip it
            if (tokens[i] == ' ')
                continue;

            // Current token is a number,
            // push it to stack for numbers
            if (tokens[i] >= '0' &&
                    tokens[i] <= '9')
            {
                StringBuffer sbuf = new
                        StringBuffer();

                // There may be more than one
                // digits in number
                while (i < tokens.length &&
                        tokens[i] >= '0' &&
                        tokens[i] <= '9')
                    sbuf.append(tokens[i++]);
                values.push(Integer.parseInt(sbuf.
                        toString()));

                // right now the i points to
                // the character next to the digit,
                // since the for loop also increases
                // the i, we would skip one
                //  token position; we need to
                // decrease the value of i by 1 to
                // correct the offset.
                i--;
            }

            // Current token is an opening brace,
            // push it to 'ops'
            else if (tokens[i] == '(')
                ops.push(tokens[i]);

                // Closing brace encountered,
                // solve entire brace
            else if (tokens[i] == ')')
            {
                while (ops.peek() != '(')
                    values.push(applyOp(ops.pop(),
                            values.pop(),
                            values.pop()));
                ops.pop();
            }

            // Current token is an operator.
            else if (tokens[i] == '+' ||
                    tokens[i] == '-' ||
                    tokens[i] == '*' ||
                    tokens[i] == '/')
            {
                // While top of 'ops' has same
                // or greater precedence to current
                // token, which is an operator.
                // Apply operator on top of 'ops'
                // to top two elements in values stack
                while (!ops.empty() &&
                        hasPrecedence(tokens[i],
                                ops.peek()))
                    values.push(applyOp(ops.pop(),
                            values.pop(),
                            values.pop()));

                // Push current token to 'ops'.
                ops.push(tokens[i]);
            }
        }

        // Entire expression has been
        // parsed at this point, apply remaining
        // ops to remaining values
        while (!ops.empty())
            values.push(applyOp(ops.pop(),
                    values.pop(),
                    values.pop()));

        // Top of 'values' contains
        // result, return it
        return values.pop();
    }

    // Returns true if 'op2' has higher
    // or same precedence as 'op1',
    // otherwise returns false.
    public static boolean hasPrecedence(
            char op1, char op2)
    {
        if (op2 == '(' || op2 == ')')
            return false;
        if ((op1 == '*' || op1 == '/') &&
                (op2 == '+' || op2 == '-'))
            return false;
        else
            return true;
    }

    // A utility method to apply an
    // operator 'op' on operands 'a'
    // and 'b'. Return the result.
    public static int applyOp(char op,
                              int b, int a)
    {
        switch (op)
        {
            case '+':
                return a + b;
            case '-':
                return a - b;
            case '*':
                return a * b;
        }
        return 0;
    }
}
